package com.goldsprite.gdxcore.utils.sorts;

import java.util.ArrayList;
import java.util.List;

public class StepByStepInsertionSort {
    static int comparisons = 0; // 统计比较次数
    static int insertions = 0;  // 统计插入次数

    public static void main(String[] args) {
        ArrayList<Float> sortedList = new ArrayList<>();
        
		long seed = 999; 
        int count = 50, size = 100;
        float[] newValues = RandomFloatArrayGenerator.generateRandomFloatArray(count, -size, size, seed);

        // 执行逐步插入排序
        for (float value : newValues) {
            insertValue(sortedList, value);
        }

        // 打印原始列表
        List<Float> originList = new ArrayList<>();
        for (float val : newValues) {
            originList.add(val);
        }
        System.out.println("Origin List: " + originList);

        // 打印排序后的列表
        System.out.println("Sorted List: " + sortedList);
        System.out.println("Total Comparisons: " + comparisons);
        System.out.println("Total Insertions: " + insertions);
    }

    /**
     * 插入值到列表中，按最小差异原则
     *
     * @param sortedList 已排序列表
     * @param value      待插入的值
     */
    public static void insertValue(ArrayList<Float> sortedList, float value) {
        if (sortedList.isEmpty()) {
            sortedList.add(value);
            insertions++;
            return;
        }

        int closestIndex = 0;
        float minDifference = Math.abs(sortedList.get(0) - value);

        // 遍历找到最小差异的位置
        for (int i = 1; i < sortedList.size(); i++) {
            comparisons++;
            float diff = Math.abs(sortedList.get(i) - value);
            if (diff < minDifference) {
                minDifference = diff;
                closestIndex = i;
            }
        }

        // 判断插入到左侧还是右侧
        if (value < sortedList.get(closestIndex)) {
            sortedList.add(closestIndex, value);
        } else {
            sortedList.add(closestIndex + 1, value);
        }
        insertions++;
    }
}
